#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 078. 子集.py
@time: 2022/1/21 12:44
@desc: https://leetcode-cn.com/problems/subsets/submissions/
> 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

@解题思路：
    1. 回溯
    2. 参考题解：
        a. https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
        b. https://leetcode-cn.com/problems/subsets/solution/hui-su-suan-fa-by-powcai-5/
    3. 相似例题：
        a. 090. 子集 II.py (含重复数字)
        b. 046. 全排列.py (不含重复数字)
        c. 047. 全排列 II.py (含重复数字)
        d. 039. 组合总和.py (不含重复元素，并可以使用多次）
        e. 040. 组合总和 II.py（含重复元素，并不可以使用多次）
    4. Ot(n*2^n), Os(n)

'''


class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)

        def backtrack(start, path):
            res.append(path)
            for i in range(start, n):
                # 固定 nums[i]
                # path.append(nums[i]) 不可以这样写，这样会使得path一直是同一个地址的变量
                # 递归固定之后的[i+1, n]位置的元素
                backtrack(i + 1, path + [nums[i]])

        res = []
        backtrack(0, [])
        return res
